#include <stdio.h>
#include <tool/ylinkedList.h>

/** Linked list item struct, declare beforehand for use */
typedef struct linkedListItem linkedListItem;

/** Linked list item struct */
struct linkedListItem {
  linkedListItem *next, *back;
  void *anItem;
};

/** Linked list data struct */
struct linkedListData {
  /** first (head), last (tail), current position,
  mark position (for action: get, add, move or delete) */
  linkedListItem *first, *last, *cur, *mark;
  /** Number of items in the list, NOT using "unsigned int" 
  require -1 value. */
  int n;
  unsigned char sizeof_linkedListItem;
  /*--- provide customized function pointers */
  /** This method is NOT provided, require customized function.
  Required to provide this when you create the linked list. */
  boolean (*freeItem)(void **anItemP);
  /** This method is NOT provided, require customized function.
  This is NOT a compulsory function pointer. */
  void *(*itemClone)(const void *anItem, const void *aControlObj);
  /** This method is NOT provided, require customized function.
  This is NOT a compulsory function pointer. */
  g_reply (*compareItem)(const void *anItem1, const void *anItem2);
};

/*======= declare internal function */
boolean ylinkedList_free(linkedList *listP);
int ylinkedList_size(const linkedList list);
boolean ylinkedList_clear(linkedList list);
/*--- traverse */
boolean ylinkedList_current(const linkedList list);
boolean ylinkedList_goNext(linkedList list);
boolean ylinkedList_goBack(linkedList list);
boolean ylinkedList_goFirst(linkedList list);
boolean ylinkedList_goLast(linkedList list);
boolean ylinkedList_goMark(linkedList list);
/*--- test */
boolean ylinkedList_isEmpty(const linkedList list);
boolean ylinkedList_isFirst(const linkedList list);
boolean ylinkedList_isLast(const linkedList list);
boolean ylinkedList_hasNext(const linkedList list);
boolean ylinkedList_hasPrevious(const linkedList list);
g_reply ylinkedList_compareItem(const linkedList list, 
    const void *anItem);
/*--- item */
void *ylinkedList_getItem(const linkedList list);
void *ylinkedList_getItemClone(const linkedList list, 
    const void *aControlObj);
boolean ylinkedList_addItemBefore(linkedList list, void *anItem);
boolean ylinkedList_addItemAfter(linkedList list, void *anItem);
boolean ylinkedList_deleteItem(linkedList list);
boolean ylinkedList_deleteItemNOTFree(linkedList list);
boolean ylinkedList_setItemNOTFree(linkedList list, void *anItem);
/*--- marked item for action */
boolean ylinkedList_mark(linkedList list);
boolean ylinkedList_clearMark(linkedList list);
void *ylinkedList_getItemMark(const linkedList list);
void *ylinkedList_getItemMarkClone(const linkedList list, 
    const void *aControlObj);
boolean ylinkedList_addItemBeforeMark(linkedList list, void *anItem);
boolean ylinkedList_addItemAfterMark(linkedList list, void *anItem);
boolean ylinkedList_deleteItemMark(linkedList list);
boolean ylinkedList_moveCurItemBeforeMark(linkedList list);
boolean ylinkedList_moveCurItemAfterMark(linkedList list);
boolean ylinkedList_moveMarkBeforeCurItem(linkedList list);
boolean ylinkedList_moveMarkAfterCurItem(linkedList list);
/*--- provide customized function */
boolean ylinkedList_setFnItemClone(linkedList list, 
    void *(*itemClone)(const void *anItem, const void *aControlObj));
boolean ylinkedList_setFnCompareItem(linkedList list, 
    g_reply (*compareItem)(const void *anItem1, const void *anItem2));
/*--- function ONLY for internal use ---*/
linkedListItem *ylinkedList_createLinkedListItem(linkedList list, 
    void *anItem);
boolean ylinkedList_initFirstLinkedListItem(linkedList list, 
    linkedListItem *lnkLItem);

/*======= directly exposed function */
/** Create a new linkedList.
<p>MUST provide a function to free an item of type <code>void *</code>.
The function is of the form <code>boolean (*freeItem)(void **)</code>.
</p>
@param freeItem the function to free an item of type <code>void *</code>.
@return a newly created and empty linkedList, 
  or <code>NULL</code> if failure.
*/
linkedList ylinkedList_create(boolean (*freeItem)(void **anItemP)) {
  if (freeItem == NULL) {return NULL;}
  linkedList list;
  FN_MALLOC_ERRMSG(list, sizeof(struct linkedList), 
      "Error: ylinkedList_create(boolean (*freeItem)(void **)) malloc(list)")
  if (list == NULL) {return NULL;}
  FN_MALLOC_ERRMSG(list->d, sizeof(struct linkedListData), 
      "Error: ylinkedList_create(boolean (*freeItem)(void **)) malloc(list->d)")
  if (list->d == NULL) {ylinkedList_free(&list); return NULL;}
  /*--- data ---*/
  list->d->n = 0;
  list->d->first = NULL;
  list->d->last = NULL;
  list->d->cur = NULL;
  list->d->mark = NULL;
  list->d->sizeof_linkedListItem = sizeof(struct linkedListItem);
  /*--- init function pointers ---*/
  list->d->freeItem = freeItem;
  list->d->itemClone = NULL;
  list->d->compareItem = NULL;
  list->free = ylinkedList_free;
  list->size = ylinkedList_size;
  list->clear = ylinkedList_clear;
  /*--- traverse */
  list->current = ylinkedList_current;
  list->goNext = ylinkedList_goNext;
  list->goBack = ylinkedList_goBack;
  list->goFirst = ylinkedList_goFirst;
  list->goLast = ylinkedList_goLast;
  list->goMark = ylinkedList_goMark;
  /*--- test */
  list->isEmpty = ylinkedList_isEmpty;
  list->isFirst = ylinkedList_isFirst;
  list->isLast = ylinkedList_isLast;
  list->hasNext = ylinkedList_hasNext;
  list->hasPrevious = ylinkedList_hasPrevious;
  list->compareItem = ylinkedList_compareItem;
  /*--- item */
  list->getItem = ylinkedList_getItem;
  list->getItemClone = ylinkedList_getItemClone;
  list->addItemBefore = ylinkedList_addItemBefore;
  list->addItemAfter = ylinkedList_addItemAfter;
  list->deleteItem = ylinkedList_deleteItem;
  list->deleteItemNOTFree = ylinkedList_deleteItemNOTFree;
  list->setItemNOTFree = ylinkedList_setItemNOTFree;
  /*--- marked item for action */
  list->mark = ylinkedList_mark;
  list->clearMark = ylinkedList_clearMark;
  list->getItemMark = ylinkedList_getItemMark;
  list->getItemMarkClone = ylinkedList_getItemMarkClone;
  list->addItemBeforeMark = ylinkedList_addItemBeforeMark;
  list->addItemAfterMark = ylinkedList_addItemAfterMark;
  list->deleteItemMark = ylinkedList_deleteItemMark;
  list->moveCurItemBeforeMark = ylinkedList_moveCurItemBeforeMark;
  list->moveCurItemAfterMark = ylinkedList_moveCurItemAfterMark;
  list->moveMarkBeforeCurItem = ylinkedList_moveMarkBeforeCurItem;
  list->moveMarkAfterCurItem = ylinkedList_moveMarkAfterCurItem;
  /*--- provide customized function */
  list->setFnItemClone = ylinkedList_setFnItemClone;
  list->setFnCompareItem = ylinkedList_setFnCompareItem;
  return list;
}

/** Create a new linkedList with this item.
<p>MUST provide a function to free an item of type <code>void *</code>.
The function is of the form <code>boolean (*freeItem)(void **)</code>.
</p>
@param anItem the item to be added.
@param freeItem the function to free an item of type <code>void *</code>.
@return a newly created linkedList with item, 
  or <code>NULL</code> if failure.
*/
linkedList ylinkedList_createWithItem(void *anItem, 
    boolean (*freeItem)(void **anItemP)) {
  linkedList list = ylinkedList_create(freeItem);
  if (list != NULL) {
    ylinkedList_initFirstLinkedListItem(list, 
      ylinkedList_createLinkedListItem(list, anItem));
  }
  return list;
}

/*======= exposed through function pointers */
/** Free this linked List from memory.
<p><b>WARNING:</b> Function will free items in the linked list as well, 
via the call to <code>boolean (*freeItem)(void **)</code>.
</p>
<p>Do NOT free anything taken out of item, 
e.g. via function pointer call to
<code>void *(*getItem)(const linkedList)</code>.
Because the linked list still points to the item. 
Thus the item in a sense still sits inside the list so
it's memory will be free by this function.
</p>
<p>However you can free the item IF 
<ul>
<li>(1) the item's library say so, such as the item's "free" function 
which is our function pointer <code>boolean (*freeItem)(void **)</code> 
couldn't and doesn't handle it.
Thus requiring external program to handle this.
e.g. Cloned data struct (which it doesn't keep track of).
</li>
<li>(2) You SHOULD free this "cloned" copy of the item cloned from the list.
The list does NOT keep track of these "clones" and shouldn't release them..
<br/>UNLESS the item does some trick to <b>keep track of it's own clone</b>, 
AND also release them via the same function pointer call to 
<code>boolean (*freeItem)(void **)</code>.
<br/><b>Advice:</b> Read the item's library for details.
</li>
</ul>
</p>
@param listP pass in the address of linked List struct pointer to be free.
@return <code>true</code> if successful otherwise <code>false</code>.
*/
boolean ylinkedList_free(linkedList *listP) {
  /* NOT critical if list is NULL, assume all's fine */
  if (*listP == NULL) {return true;}
  if ((*listP)->d != NULL) {
    /* NOT critical if unable to clear list, assume all's fine */
    ylinkedList_clear(*listP);
    /* free the linkedListData struct */
    free((*listP)->d);
    (*listP)->d = NULL;
  } /* if ((*listP)->d != NULL) */
  /* free the linkedList struct */
  free(*listP);
  *listP = NULL;
  return true;
}

/** Returns the number of elements in this list.
@param list the linked list.
@return Returns the number of elements in this list or -1 if failure.
*/
int ylinkedList_size(const linkedList list) {
  if (list == NULL || list->d == NULL) {
    return -1;
  }
  return list->d->n;
}

/** Removes all of the elements from this list.
@param list the linked list.
@return <code>true</code> if successful 
  otherwise <code>false</code> nothing to remove.
*/
boolean ylinkedList_clear(linkedList list) {
  if (list == NULL || list->d == NULL) {
    return false;
  }
  if (list->d->first == NULL) {  
    /* is this an empty list? try another method */
    if (list->d->cur == NULL) {
      /* list is empty or something is wrong! anyway last try */
      if (list->d->last == NULL) {
        /* exhaust all revenue, give up, do nothing here */
      } else {
        list->d->cur = list->d->last;
      }
    } /* else: just use list->d->cur */
  } else {
    list->d->cur = list->d->first;
  }
  /* safeguard: rewind to the 1st item if possible */
  while (list->d->cur != NULL) {
    if (list->d->cur->back == NULL) {
      break;
    } else {
      list->d->cur = list->d->cur->back;
    }
  }
  /* go through the whole list */
  while (list->d->cur != NULL) {
    /* prepare */
    /* use the "mark" pointer as a "previous" pointer to current position */
    list->d->mark = list->d->cur;
    /* MUST move current to next item 1st! before freeing memory */
    list->d->cur = list->d->cur->next;
    /* free linked list item's content */
    if (list->d->freeItem(&list->d->mark->anItem) == false) {
      /* possible memory leak */
      perror("Error: ylinkedList_free(linkedList *) list->d->freeItem(&list->d->mark->anItem)");
    }
    /* free linked list item, itself i.e. linkedListItem struct */
    free(list->d->mark);
  }
  list->d->n = 0;
  list->d->first = NULL;
  list->d->last = NULL;
  list->d->cur = NULL;
  list->d->mark = NULL;
  return true;
}

/*--- traverse */
/** If the list currently point at something.
@param list the linked list.
@return <code>true</code> if successful otherwise <code>false</code>.
*/
boolean ylinkedList_current(const linkedList list) {
  /* currently must point to something */
  if (list == NULL || list->d == NULL || list->d->cur == NULL) {
    return false;
  }
  return true;
}

/** Move to next item. Successful if next in list point at something, 
otherwise stay at the tail of the list.
@param list the linked list.
@return <code>true</code> if successful otherwise <code>false</code>.
*/
boolean ylinkedList_goNext(linkedList list) {
  if (list == NULL || list->d == NULL || list->d->cur == NULL 
    || list->d->cur->next == NULL) {
    return false;
  }
  list->d->cur = list->d->cur->next;
  return true;
}

/** Move back a item. Successful if previous in list point at something, 
otherwise stay at the head of the list.
@param list the linked list.
@return <code>true</code> if successful otherwise <code>false</code>.
*/
boolean ylinkedList_goBack(linkedList list) {
  if (list == NULL || list->d == NULL || list->d->cur == NULL 
    || list->d->cur->back == NULL) {
    return false;
  }
  list->d->cur = list->d->cur->back;
  return true;
}

/** Move to the first item in the list. 
@param list the linked list.
@return <code>true</code> if successful otherwise <code>false</code>.
*/
boolean ylinkedList_goFirst(linkedList list) {
  if (list == NULL || list->d == NULL || list->d->first == NULL) {
    return false;
  }
  list->d->cur = list->d->first;
  return true;
}

/** Move to the last item in the list. 
@param list the linked list.
@return <code>true</code> if successful otherwise <code>false</code>.
*/
boolean ylinkedList_goLast(linkedList list) {
  if (list == NULL || list->d == NULL || list->d->last == NULL) {
    return false;
  }
  list->d->cur = list->d->last;
  return true;
}

/** Move to the "mark" item in the list. 
@param list the linked list.
@return <code>true</code> if successful otherwise <code>false</code>.
*/
boolean ylinkedList_goMark(linkedList list) {
  if (list == NULL || list->d == NULL || list->d->mark == NULL) {
    return false;
  }
  list->d->cur = list->d->mark;
  return true;
}

/*--- test */
/** Tests if this list has no elements.
@param list the linked list.
@return <code>true</code> if successful otherwise <code>false</code>.
*/
boolean ylinkedList_isEmpty(const linkedList list) {
  /* currently must point to something */
  if (list == NULL || list->d == NULL || list->d->cur == NULL) {
    return true;
  }
  return false;
}

/** Are we currently pointing to the first item in the list?
@param list the linked list.
@return true if pointing to the first item, false otherwise.
*/
boolean ylinkedList_isFirst(const linkedList list) {
  if (list == NULL || list->d == NULL || list->d->cur == NULL) {
    return false;
  }
  if (list->d->cur == list->d->first) {
    return true;
  }
  return false;
}

/** Are we currently pointing to the last item in the list?
@param list the linked list.
@return true if pointing to the last item, false otherwise.
*/
boolean ylinkedList_isLast(const linkedList list) {
  if (list == NULL || list->d == NULL || list->d->cur == NULL) {
    return false;
  }
  if (list->d->cur == list->d->last) {
    return true;
  }
  return false;
}

/** Is there another item after current item in the list?
@param list the linked list.
@return true if successful, false otherwise.
*/
boolean ylinkedList_hasNext(const linkedList list) {
  if (list == NULL || list->d == NULL || list->d->cur == NULL
    || list->d->cur->next == NULL) {
    return false;
  }
  return true;
}

/** Is there another item before current item in the list?
@param list the linked list.
@return true if successful, false otherwise.
*/
boolean ylinkedList_hasPrevious(const linkedList list) {
  if (list == NULL || list->d == NULL || list->d->cur == NULL
    || list->d->cur->back == NULL) {
    return false;
  }
  return true;
}

/** Compare a given item against the item currently 
pointing to within in the list.
<p>MUST provide the function of the form 
<code>g_reply (*compareItem)(const void *, const void *)</code>.
through <code>setFnCompareItem(..)</code> beforehand to 
able to use this function
</p>
<p><code>compareItem</code> should return <code>g_replyEqual</code> 
if <code>anItem</code> and list's item are equal.
Returns <code>g_replyLesser</code> or <code>g_replyGreater</code> 
if <code>anItem</code> is less than or greater than 
list's item respectively.
</p>
<p>This is a customized function provided by the item's library 
and is NOT compulsory.
</p>
@param list the linked list.
@param anItem the given item to compare 
  against the current item within the list.
@return Return <code>g_replyEqual</code> 
  if <code>anItem</code> and list's item are equal.
  Returns <code>g_replyLesser</code> or <code>g_replyGreater</code> 
  if <code>anItem</code> is less than or greater than 
  list's item respectively.
  Otherwise <code>g_replyFail</code> for failure.
*/
g_reply ylinkedList_compareItem(const linkedList list, 
    const void *anItem) {
  if (list == NULL || list->d == NULL || list->d->cur == NULL
      || list->compareItem == NULL) {
    return g_replyFail;
  }
  /* the 1st parameter MUST be the given item, 
    2nd parameter MUST be the item from the list */
  return list->d->compareItem(anItem, list->d->cur->anItem);
}

/*--- item */
/** Obtain the item of the currently pointing item in the list. 
<p><b>WARNING:</b> Function will free items in the linked list as well, 
via the call to <code>boolean (*freeItem)(void **)</code>.
</p>
<p>Do NOT free anything taken out of item, 
e.g. via function pointer call to
<code>void *(*getItem)(const linkedList)</code>.
Because the linked list still points to the item. 
Thus the item in a sense still sits inside the list so
it's memory will be free by this function.
</p>
<p>However you can free the item IF 
<ul>
<li>(1) the item's library say so, such as the item's "free" function 
which is our function pointer <code>boolean (*freeItem)(void **)</code> 
couldn't and doesn't handle it.
Thus requiring external program to handle this.
e.g. Cloned data struct (which it doesn't keep track of).
</li>
<li>(2) You SHOULD free this "cloned" copy of the item cloned from the list.
The list does NOT keep track of these "clones" and shouldn't release them..
<br/>UNLESS the item does some trick to <b>keep track of it's own clone</b>, 
AND also release them via the same function pointer call to 
<code>boolean (*freeItem)(void **)</code>.
<br/><b>Advice:</b> Read the item's library details.
</li>
</ul>
</p>
@param list the linked list.
@return the currently pointing item in the list.
*/
void *ylinkedList_getItem(const linkedList list) {
  if (list == NULL || list->d == NULL || list->d->cur == NULL) {
    return NULL;
  }
  return list->d->cur->anItem;
}

/** Obtain a "cloned" copy of the item currently pointing to in the list. 
<p>This is a customized function provided by the item's library 
and is NOT compulsory.
</p>
<p>The customized function is given to the list via function pointer
<code>boolean (*setFnItemClone)(linkedList, 
    void *(*itemClone)(const void *, const void *))</code>.
</p>
<p>You SHOULD free this "cloned" copy of the item cloned from the list.
The list does NOT keep track of these "clones" and shouldn't release them..
<br/>UNLESS the item does some trick to <b>keep track of it's own clone</b>, 
AND also release them via the same function pointer call to 
<code>boolean (*freeItem)(void **)</code>.
<br/><b>Advice:</b> Read the item's library for details.
</p>
@param list the linked list.
@param aControlObj an object that customized function may work with,
  e.g. provide cloning ability, other facility and perform other duty.
@return a "cloned" copy of the item currently pointing to in the list, or
  <code>NULL</code> if failure.
*/
void *ylinkedList_getItemClone(const linkedList list, 
    const void *aControlObj) {
  if (list == NULL || list->d == NULL || list->d->itemClone == NULL
    || list->d->cur == NULL) {
    return NULL;
  }
  return list->d->itemClone(list->d->cur->anItem, aControlObj);
}

/** Add this item before the current one in the list.
Allow item to be <code>NULL</code>.
<p><b>WARNING:</b> once the item is added into this linked list.
The linked list will handle freeing the item's memory, 
via call to function pointer <code>boolean (*freeItem)(void **)</code>.
</p>
<p><b>NEVER release memory of the item, once you've added into the list, 
UNLESS your copy is a clone of the one inside the list.</b> 
You have to handle freeing memory of the clone.
The list will handle freeing the item it is pointing to.
</p>
<p>The 2 possibility of item memory will be release by the linked list are 
when (1) the item is deleted via call to function pointer
<code>boolean (*deleteItem)(linkedList)</code>,
or (2) freeing linked list memory via call to function pointer
<code>boolean (*free)(linkedList *)</code>.
</p>
@param list the linked list.
@param anItem the item to be added.
@return true if successfully added the item, false otherwise.
*/
boolean ylinkedList_addItemBefore(linkedList list, void *anItem) {
  if (list == NULL || list->d == NULL) {return false;}
  linkedListItem *lnkLItem = ylinkedList_createLinkedListItem(list, anItem);
  if (lnkLItem == NULL) {return false;}
  if (list->d->cur == NULL) {
    /* this is the first item in the list! */
    return ylinkedList_initFirstLinkedListItem(list, lnkLItem);
  }
  if (list->d->cur->back == NULL) {
    /* new item will be first in the list */
    list->d->first = lnkLItem;
  } else {
    /* remember previous item */
    lnkLItem->back = list->d->cur->back;
    list->d->cur->back->next = lnkLItem;
  }
  /* add new item before current */
  list->d->cur->back = lnkLItem;
  lnkLItem->next = list->d->cur;
  /* new item becomes what we point to now */
  list->d->cur = lnkLItem;
  list->d->n++;
  return true;
}

/** Add this item after the current one in the list.
Allow item to be <code>NULL</code>.
<p><b>WARNING:</b> once the item is added into this linked list.
The linked list will handle freeing the item's memory, 
via call to function pointer <code>boolean (*freeItem)(void **)</code>.
</p>
<p><b>NEVER release memory of the item, once you've added into the list, 
UNLESS your copy is a clone of the one inside the list.</b> 
You have to handle freeing memory of the clone.
The list will handle freeing the item it is pointing to.
</p>
<p>The 2 possibility of item memory will be release by the linked list are 
when (1) the item is deleted via call to function pointer
<code>boolean (*deleteItem)(linkedList)</code>,
or (2) freeing linked list memory via call to function pointer
<code>boolean (*free)(linkedList *)</code>.
</p>
@param list the linked list.
@param anItem the item to be added.
@return true if successfully added the item, false otherwise.
*/
boolean ylinkedList_addItemAfter(linkedList list, void *anItem) {
  if (list == NULL || list->d == NULL) {return false;}
  linkedListItem *lnkLItem = ylinkedList_createLinkedListItem(list, anItem);
  if (lnkLItem == NULL) {return false;}
  if (list->d->cur == NULL) {
    /* this is the first item in the list! */
    return ylinkedList_initFirstLinkedListItem(list, lnkLItem);
  }
  if (list->d->cur->next == NULL) {
    /* new item will be last in the list */
    list->d->last = lnkLItem;
  } else {
    /* remember next item */
    lnkLItem->next = list->d->cur->next;
    list->d->cur->next->back = lnkLItem;
  }
  /* add new item after current */
  list->d->cur->next = lnkLItem;
  lnkLItem->back = list->d->cur;
  /* new item becomes what we point to now */
  list->d->cur = lnkLItem;
  list->d->n++;
  return true;
}

/** Delete the current item from the list. 
After deletion the new current item will become the next item if it exist, 
otherwise the new current item will become the item in front if it exist.
If no item exist in front or to the back, the list is empty, 
current has no item and points to <code>NULL</code>.
@param list the linked list.
@return <code>true</code> if successfully otherwise <code>false</code>.
*/
boolean ylinkedList_deleteItem(linkedList list) {
  if (list == NULL || list->d == NULL || list->d->cur == NULL) {
    return false;
  }
  linkedListItem *lnkLItemToDelete = list->d->cur;
  if (list->d->cur->back != NULL && list->d->cur->next != NULL) {
    /* reconnect the links of item in front & next item */
    list->d->cur->back->next = list->d->cur->next;
    list->d->cur->next->back = list->d->cur->back;
    /* current becomes next item */
    list->d->cur = list->d->cur->next;
  } else if (list->d->cur->back != NULL && list->d->cur->next == NULL) {
    /* current becomes item in front */
    list->d->cur = list->d->cur->back;
    /* item in front also becomes last item */
    list->d->last = list->d->cur->back;
  } else if (list->d->cur->back == NULL && list->d->cur->next != NULL) {
    /* current becomes next item */
    list->d->cur = list->d->cur->next;
    /* next item also becomes first item */
    list->d->first = list->d->cur->next;
  } else {  /* list->d->cur->back == NULL && list->d->cur->next == NULL */
    list->d->first = NULL;
    list->d->last = NULL;
    list->d->cur = NULL;
  }
  /* free linked list item's content */
  if (list->d->freeItem(&lnkLItemToDelete->anItem) == false) {
    /* possible memory leak */
    perror("Error: ylinkedList_deleteItem(linkedList) list->d->freeItem(&lnkLItemToDelete->anItem) == false");
  }
  /* free linked list item, itself */
  free(lnkLItemToDelete);
  list->d->n--;
  return true;
}

/** Delete the current item from the list 
BUT will NOT free the deleted item from memory!
After deletion the new current item will become the next item if it exist, 
otherwise the new current item will become the item in front if it exist.
If no item exist in front or to the back, the list is empty, 
current has no item and points to <code>NULL</code>.
@param list the linked list.
@return <code>true</code> if successfully otherwise <code>false</code>.
*/
boolean ylinkedList_deleteItemNOTFree(linkedList list) {
  if (list == NULL || list->d == NULL || list->d->cur == NULL) {
    return false;
  }
  linkedListItem *lnkLItemToDelete = list->d->cur;
  if (list->d->cur->back != NULL && list->d->cur->next != NULL) {
    /* reconnect the links of item in front & next item */
    list->d->cur->back->next = list->d->cur->next;
    list->d->cur->next->back = list->d->cur->back;
    /* current becomes next item */
    list->d->cur = list->d->cur->next;
  } else if (list->d->cur->back != NULL && list->d->cur->next == NULL) {
    /* current becomes item in front */
    list->d->cur = list->d->cur->back;
    /* item in front also becomes last item */
    list->d->last = list->d->cur->back;
  } else if (list->d->cur->back == NULL && list->d->cur->next != NULL) {
    /* current becomes next item */
    list->d->cur = list->d->cur->next;
    /* next item also becomes first item */
    list->d->first = list->d->cur->next;
  } else {  /* list->d->cur->back == NULL && list->d->cur->next == NULL */
    list->d->first = NULL;
    list->d->last = NULL;
    list->d->cur = NULL;
  }
  /* will NOT free linked list item's content */
  /* free linked list item, itself */
  free(lnkLItemToDelete);
  list->d->n--;
  return true;
}

/** Set a new item over the current item in the list, 
BUT will NOT free the previous item from memory!
Note this is NOT adding.
@param list the linked list.
@param anItem the item to be added.
@return <code>true</code> if successfully, 
  or <code>false</code> if failure occurs.
*/
boolean ylinkedList_setItemNOTFree(linkedList list, void *anItem) {
  if (list == NULL || list->d == NULL || list->d->cur == NULL) {
    return false;
  }
  list->d->cur->anItem = anItem;
  return true;
}

/*--- marked item for action */
/** Mark the current item as "mark" in the list.
Allow action such as get, move, add & delete 
to be taken relative to this "mark" item.
@param list the linked list.
@return <code>true</code> if successfully otherwise <code>false</code>.
*/
boolean ylinkedList_mark(linkedList list) {
  if (list == NULL || list->d == NULL) {return false;}
  list->d->mark = list->d->cur;
  return true;
}

/** Clear the "mark", so that "mark" will point to nothing.
Previous "mark" item is NOT affected.
Action afterwards such as get, move, add & delete 
relative to this cleared "mark" will NOT be successful.
@param list the linked list.
@return <code>true</code> if successfully otherwise <code>false</code>.
*/
boolean ylinkedList_clearMark(linkedList list) {
  if (list == NULL || list->d == NULL) {return false;}
  list->d->mark = NULL;
  return true;
}

/** Obtain the item of at the marked position in the list. 
<p><b>WARNING:</b> Function will free items in the linked list as well, 
via the call to <code>boolean (*freeItem)(void **)</code>.
</p>
<p>Do NOT free anything taken out of item, 
e.g. via function pointer call to
<code>void *(*getItem)(const linkedList)</code>.
Because the linked list still points to the item. 
Thus the item in a sense still sits inside the list so
it's memory will be free by this function.
</p>
<p>However you can free the item IF 
<ul>
<li>(1) the item's library say so, such as the item's "free" function 
which is our function pointer <code>boolean (*freeItem)(void **)</code> 
couldn't and doesn't handle it.
Thus requiring external program to handle this.
e.g. Cloned data struct (which it doesn't keep track of).
</li>
<li>(2) You SHOULD free this "cloned" copy of the item cloned from the list.
The list does NOT keep track of these "clones" and shouldn't release them..
<br/>UNLESS the item does some trick to <b>keep track of it's own clone</b>, 
AND also release them via the same function pointer call to 
<code>boolean (*freeItem)(void **)</code>.
<br/><b>Advice:</b> Read the item's library details.
</li>
</ul>
</p>
@param list the linked list.
@return the item at the marked position in the list.
*/
void *ylinkedList_getItemMark(const linkedList list) {
  if (list == NULL || list->d == NULL || list->d->mark == NULL) {
    return NULL;
  }
  return list->d->mark->anItem;
}

/** Obtain a "cloned" copy of the item at the marked position in the list. 
<p>This is a customized function provided by the item's library 
and is NOT compulsory.
</p>
<p>The customized function is given to the list via function pointer
<code>boolean (*setFnItemClone)(linkedList, 
    void *(*itemClone)(const void *, const void *))</code>.
</p>
<p>You SHOULD free this "cloned" copy of the item cloned from the list.
The list does NOT keep track of these "clones" and shouldn't release them..
<br/>UNLESS the item does some trick to <b>keep track of it's own clone</b>, 
AND also release them via the same function pointer call to 
<code>boolean (*freeItem)(void **)</code>.
<br/><b>Advice:</b> Read the item's library for details.
</p>
@param list the linked list.
@param aControlObj an object that customized function may work with,
  e.g. provide cloning ability, other facility and perform other duty.
@return a "cloned" copy of the item at the marked position to in the list, or
  <code>NULL</code> if failure.
*/
void *ylinkedList_getItemMarkClone(const linkedList list, 
    const void *aControlObj) {
  if (list == NULL || list->d == NULL || list->d->itemClone == NULL
    || list->d->mark == NULL) {
    return NULL;
  }
  return list->d->itemClone(list->d->mark->anItem, aControlObj);
}

/** Add this item before the marked position in the list.
Allow item to be <code>NULL</code>.
<p><b>WARNING:</b> once the item is added into this linked list.
The linked list will handle freeing the item's memory, 
via call to function pointer <code>boolean (*freeItem)(void **)</code>.
</p>
<p><b>NEVER release memory of the item, once you've added into the list, 
UNLESS your copy is a clone of the one inside the list.</b> 
You have to handle freeing memory of the clone.
The list will handle freeing the item it is pointing to.
</p>
<p>The 2 possibility of item memory will be release by the linked list are 
when (1) the item is deleted via call to function pointer
<code>boolean (*deleteItem)(linkedList)</code>,
or (2) freeing linked list memory via call to function pointer
<code>boolean (*free)(linkedList *)</code>.
</p>
@param list the linked list.
@param anItem the item to be added.
@return true if successfully added the item, false otherwise.
*/
boolean ylinkedList_addItemBeforeMark(linkedList list, void *anItem) {
  if (list == NULL || list->d == NULL || list->d->mark == NULL) {
    return false;
  }
  /* use HACK method: remember cur pointer position */
  linkedListItem *cur = list->d->cur;
  /* prepare mark position for insert */
  list->d->cur = list->d->mark;
  /* does the insert, 
    however mark position will NOT move! */
  boolean isOK = ylinkedList_addItemBefore(list, anItem);
  /* restore cur pointer position, 
    cur position have NOT move either! */
  list->d->cur = cur;
  return isOK;
}

/** Add this item after the marked position in the list.
Allow item to be <code>NULL</code>.
<p><b>WARNING:</b> once the item is added into this linked list.
The linked list will handle freeing the item's memory, 
via call to function pointer <code>boolean (*freeItem)(void **)</code>.
</p>
<p><b>NEVER release memory of the item, once you've added into the list, 
UNLESS your copy is a clone of the one inside the list.</b> 
You have to handle freeing memory of the clone.
The list will handle freeing the item it is pointing to.
</p>
<p>The 2 possibility of item memory will be release by the linked list are 
when (1) the item is deleted via call to function pointer
<code>boolean (*deleteItem)(linkedList)</code>,
or (2) freeing linked list memory via call to function pointer
<code>boolean (*free)(linkedList *)</code>.
</p>
@param list the linked list.
@param anItem the item to be added.
@return true if successfully added the item, false otherwise.
*/
boolean ylinkedList_addItemAfterMark(linkedList list, void *anItem) {
  if (list == NULL || list->d == NULL || list->d->mark == NULL) {
    return false;
  }
  /* use HACK method: remember cur pointer position */
  linkedListItem *cur = list->d->cur;
  /* prepare mark position for insert */
  list->d->cur = list->d->mark;
  /* does the insert, 
    however mark position will NOT move! */
  boolean isOK = ylinkedList_addItemAfter(list, anItem);
  /* restore cur pointer position, 
    cur position have NOT move either! */
  list->d->cur = cur;
  return isOK;
}

/** Delete the item at the marked position from the list. 
If marked position is the same as currently pointing item 
and a successful delete has occurred, 
the new currently pointing item will move accordingly.
The marked position will be cleared after a successful delete.
@param list the linked list.
@return <code>true</code> if successfully otherwise <code>false</code>.
*/
boolean ylinkedList_deleteItemMark(linkedList list) {
  if (list == NULL || list->d == NULL || list->d->mark == NULL) {
    return false;
  }
  /* use HACK method: */
  linkedListItem *cur;
  /* mark == cur position */
  if (list->d->cur == list->d->mark) {
    /* do NOT restore position of both pointers after delete! 
      delete the item at cur position */
    cur = NULL;
  } else {
    /* There could be a case in here that
      list->d->cur pass in NULL,
      although this should NOT have occur 
      but if it did it's a bug.
      
      remember cur pointer position */
    cur = list->d->cur;
    /* prepare mark position for delete */
    list->d->cur = list->d->mark;
  }
  /* delete */
  boolean isOK = ylinkedList_deleteItem(list);
  
  /* There could be a case list->d->cur pass in NULL,
    although this should NOT occur, 
    so that cur is NEVER restore. */
  if (cur != NULL) {
    /* restore cur pointer position, 
      cur position have NOT move either! */
    list->d->cur = cur;
  }
  if (isOK == true) {
    /* a successful delete has occurred 
      MUST clear mark position */
    list->d->mark = NULL;
  }
  return isOK;
}

/** Move the current item before the "mark" item.
@param list the linked list.
@return <code>true</code> if successfully otherwise <code>false</code>.
*/
boolean ylinkedList_moveCurItemBeforeMark(linkedList list) {
  if (list == NULL || list->d == NULL || list->d->cur == NULL
      || list->d->mark == NULL || list->d->cur == list->d->mark) {
    return false;
  }
  /* already in position */
  if (list->d->cur->next == list->d->mark) {
    return true;
  }
  /* connect cur pointer's back & next items */
  list->d->cur->back->next = list->d->cur->next;
  list->d->cur->next->back = list->d->cur->back;
  /* move cur item between mark's back & mark item */
  list->d->cur->next = list->d->mark;
  list->d->cur->back = list->d->mark->back;
  /* connect mark's back & mark item to cur pointer's item */
  list->d->mark->back->next = list->d->cur;
  list->d->mark->back = list->d->cur;
  return true;
}

/** Move the current item after the "mark" item.
@param list the linked list.
@return <code>true</code> if successfully otherwise <code>false</code>.
*/
boolean ylinkedList_moveCurItemAfterMark(linkedList list) {
  if (list == NULL || list->d == NULL || list->d->cur == NULL
      || list->d->mark == NULL || list->d->cur == list->d->mark) {
    return false;
  }
  /* already in position */
  if (list->d->mark == list->d->cur->back) {
    return true;
  }
  /* connect cur pointer's back & next items */
  list->d->cur->back->next = list->d->cur->next;
  list->d->cur->next->back = list->d->cur->back;
  /* move cur item between mark & mark's next item */
  list->d->cur->next = list->d->mark->next;
  list->d->cur->back = list->d->mark;
  /* connect mark & mark's next item to cur pointer's item */
  list->d->mark->next->back = list->d->cur;
  list->d->mark->next = list->d->cur;
  return true;
}

/** Move the "mark" item before the current item.
@param list the linked list.
@return <code>true</code> if successfully otherwise <code>false</code>.
*/
boolean ylinkedList_moveMarkBeforeCurItem(linkedList list) {
  if (list == NULL || list->d == NULL || list->d->mark == NULL
      || list->d->cur == NULL || list->d->mark == list->d->cur) {
    return false;
  }
  /* already in position */
  if (list->d->mark->next == list->d->cur) {
    return true;
  }
  /* connect mark pointer's back & next items */
  list->d->mark->back->next = list->d->mark->next;
  list->d->mark->next->back = list->d->mark->back;
  /* move mark item between cur's back & cur item */
  list->d->mark->next = list->d->cur;
  list->d->mark->back = list->d->cur->back;
  /* connect cur's back & cur item to mark pointer's item */
  list->d->cur->back->next = list->d->mark;
  list->d->cur->back = list->d->mark;
  return true;
}

/** Move the "mark" item after the current item.
@param list the linked list.
@return <code>true</code> if successfully otherwise <code>false</code>.
*/
boolean ylinkedList_moveMarkAfterCurItem(linkedList list) {
  if (list == NULL || list->d == NULL || list->d->mark == NULL
      || list->d->cur == NULL || list->d->mark == list->d->cur) {
    return false;
  }
  /* already in position */
  if (list->d->cur == list->d->mark->back) {
    return true;
  }
  /* connect mark pointer's back & next items */
  list->d->mark->back->next = list->d->mark->next;
  list->d->mark->next->back = list->d->mark->back;
  /* move mark item between cur & cur's next item */
  list->d->mark->next = list->d->cur->next;
  list->d->mark->back = list->d->cur;
  /* connect cur & cur's next item to mark pointer's item */
  list->d->cur->next->back = list->d->mark;
  list->d->cur->next = list->d->mark;
  return true;
}

/*--- provide customized function */
/** Provide a function to clone an item of type <code>void *</code>.
The function is of the form 
<code>void *(*itemClone)(const void *, const void *)</code>.
<p>This is a customized function provided by the item's library 
and is NOT compulsory.
</p>
<p>You SHOULD free this "cloned" copy of the item cloned from the list.
The list does NOT keep track of these "clones" and shouldn't release them..
<br/>UNLESS the item does some trick to <b>keep track of it's own clone</b>, 
AND also release them via the same function pointer call to 
<code>boolean (*freeItem)(void **)</code>.
<br/><b>Advice:</b> Read the item's library for details.
</p>
@param list the linked list.
@param itemClone the function to clone an item of type <code>void *</code>.
@return <code>true</code> if successful otherwise <code>false</code>.
*/
boolean ylinkedList_setFnItemClone(linkedList list, 
    void *(*itemClone)(const void *anItem, const void *aControlObj)) {
  if (list == NULL || list->d == NULL || itemClone == NULL) {
    return false;
  }
  list->d->itemClone = itemClone;
  return true;
}

/** Provide a function to compare two items of type <code>void *</code>.
The function is of the form 
<code>g_reply (*compareItem)(const void *, const void *)</code>.
<p>This function will be used for comparing a given item against 
the item currently pointing to within in the list.
<br/><code>anItem1</code> is the given item.
<br/><code>anItem2</code> is the current item within the list.
</p>
<p><code>compareItem</code> should return <code>g_replyEqual</code> 
if <code>anItem1</code> and <code>anItem2</code> are equal.
Returns <code>g_replyLesser</code> or <code>g_replyGreater</code> 
if <code>anItem1</code> is less than or greater than 
<code>anItem2</code> respectively.
</p>
<p>This is a customized function provided by the item's library 
and is NOT compulsory.
</p>
@param list the linked list.
@param compareItem the function to compare 
  two items of type <code>void *</code>.
@return <code>true</code> if successful otherwise <code>false</code>.
*/
boolean ylinkedList_setFnCompareItem(linkedList list, 
    g_reply (*compareItem)(const void *anItem1, const void *anItem2)) {
  if (list == NULL || list->d == NULL || compareItem == NULL) {
    return false;
  }
  list->d->compareItem = compareItem;
  return true;
}

/*======= function ONLY for internal use */
/** Initialize the empty list with the 1st item.
This function is for internal use ONLY, do NOT expose this.
@param list the linked list.
@param lnkLItem the linked list item.
@return <code>true</code> if successful otherwise <code>false</code>.
*/
boolean ylinkedList_initFirstLinkedListItem(linkedList list, 
    linkedListItem *lnkLItem) {
  if (list == NULL || list->d == NULL) {return false;}
  if (lnkLItem == NULL) {return false;}
  list->d->first = lnkLItem;
  list->d->last = lnkLItem;
  list->d->cur = lnkLItem;
  list->d->n++;
  return true;
}

/** Create a new linkedListItem with this item.
Allow item to be <code>NULL</code>.
This function is for internal use ONLY, do NOT expose this.
@param list the linked list.
@param anItem the item to be added.
@return a newly created linkedListItem with item, 
or <code>NULL</code> if failure.
*/
linkedListItem *ylinkedList_createLinkedListItem(linkedList list, 
    void *anItem) {
  linkedListItem *lnkLItem;
  FN_MALLOC_ERRMSG(lnkLItem, list->d->sizeof_linkedListItem, 
      "Error: ylinkedList_createLinkedListItem(linkedList, void *) malloc(lnkLItem)")
  if (lnkLItem == NULL) {return NULL;}
  lnkLItem->next = NULL;
  lnkLItem->back = NULL;
  lnkLItem->anItem = anItem;
  return lnkLItem;
}
